package 中等.二分查找;

/**
 * 峰值元素是指其值严格大于左右相邻值的元素。
 * 给你一个整数数组 nums，找到峰值元素并返回其索引。
 * 数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
 * 你可以假设 nums[-1] = nums[n] = -∞ 。
 * 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-peak-element
 */
public class 寻找峰值_162 {

    public static void main(String[] args) {

    }

    /**
     * 因为 nums[i] != nums[i + 1]
     * 那么对于某一个索引 nums[j] 如果 nums[j+1] > nums[j]
     * 那么 [j+1,end] 一定存在一个最大值满足峰值
     */
    public int findPeakElement(int[] nums) {
        if (nums.length == 1) return 0;

        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid == 0 && nums[mid] > nums[mid + 1] ||
                    mid == nums.length - 1 && nums[mid] > nums[mid - 1] ||
                    nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
                return mid;
            }

            if (nums[mid + 1] > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }

}
